# -*- coding: UTF-8 -*-

numbers = [35, 33, 42, 10, 14, 19, 27, 44, 26, 31]
length = len(numbers)


def quick_sort(left, right, nums):
    if left >= right:
        return
    else:
        pivot = nums[right]
        pivot_index = partition(left, right, pivot, nums)
        quick_sort(left, pivot_index - 1, nums)
        quick_sort(pivot_index + 1, right, nums)


def partition(left, right, pivot, nums):
    lo = left
    hi = right - 1  # 不包含基准元素位置

    while True:
        # 移动 `lo` 位置找到大于，`pivot` 的元素。
        for i in range(lo, hi + 1):
            lo = i
            if nums[i] > pivot:
                break
        # 移动 `hi` 位置找到小于，`pivot` 的元素。
        for j in range(hi, lo - 1, -1):
            hi = j
            if nums[j] < pivot:
                break

        # 当移动的点交叉，本次迁移完成。退出
        if lo >= hi:
            break
        else:
            # 交换两个元素位置。
            print("交换:", nums[lo], nums[hi], "\n")
            nums[lo], nums[hi] = nums[hi], nums[lo]

    # 当 `hi` 和 `lo` 交叉以后，数据已经通过 `pivot` 分割成左右两段。那么 `pivot` 就需要移动到交叉点的位置。
    if lo != right:
        print("交换:", nums[lo], nums[right], "\n")
        nums[lo], nums[right] = nums[right], nums[lo]

    return lo


print("排序前:")
print(numbers)
quick_sort(0, length - 1, numbers)

print("排序后:", numbers)
